Today's computer have to perform arithmetic operations, e.g. addition, multiplication, etc., with numbers and values that grow larger and larger such that the computer is not able to execute the computation in polynomial time. As there is an attempt of increasing security this trend will continue. When, for example, performing an ordinary operation of arithmetic with shares, the size of the shares increases and further computations become more and more inefficient. However there is currently no method available that reduces these shares by a shared integer such that the correct value modulo the integer can still be recombined.
Hence a scheme for reducing a known value modulo a shared secret value will be highly useful both for reducing a value and reducing a share of a value.
The size of a key in the so-called RSA scheme typically refers to the size of the modulus. N. Ronald Rivest, Adi Shamir, and Leonard Adleman developed the RSA scheme in 1977 that is a public-key cryptosystem that offers both encryption and digital signatures, i.e. authentication. RSA stands for the first letter in each of its inventors' last names. In the RSA scheme two primes, p and q, which compose the modulus N, should be of roughly equal length; this makes the modulus harder to factor than if one of the primes is much smaller than the other. If one chooses to use a 768-bit modulus, the primes should each have a length of approximately 384 bits. If the two primes are extremely close or their difference is close to any predetermined amount, then there is a potential security risk, but the probability that two randomly chosen primes are so close is negligible.
The best size for a modulus depends on one's security needs. The larger the modulus, the greater the security, but also the slower the RSA scheme operations. One should choose a modulus length upon consideration, first, of the value of the protected data and how long it needs to be protected, and, second, of how powerful one's potential threats might be.
Nevertheless, situations may occur where one has to compute in a group Zφ with a modulus φ shared secretly. For example, consider N to be the publicly known RSA modulus and φ=φ (N) to be the Euler function of N. Thus, the previously mentioned situation appears namely that on the one hand the security of the RSA scheme is based on the assumption that φ(N) remains secret but on the other hand the public key of the encryption scheme is chosen from the group Zφ, from which also the secret key is computed. Given a shared integer φ and a prime e, a protocol for computing a sharing of e−1 mod φ is known. This protocol allows the calculation of the greatest common divisor (gcd) of a public and a shared secret value, i.e., gcd(e, φ) in a distributed way.
Considered is the case where k parties or participating network devices hold additive shares of c, that is publicly known, and a shared integer and φ. Together they wish to compute an additive sharing of a value d that is congruent to c mod φ and has a size about φ without revealing anything about φ.
There is a need for a scheme for reducing a publicly known value by an unknown modulus that takes into consideration the distributed structure of an underlying system with k parties or participating network devices.